﻿using System;
using System.Collections.Generic;
using System.Net;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Documents;
using System.Windows.Ink;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Animation;
using System.Windows.Shapes;

namespace UI.Dendrogram
{
    public class DendrogramUtil
    {
        private const double LeafLength = 80;
        private const double Edge = 0;
        //private const double MinLeafHeight = 20;
        //private const double MinBranchLen = 30;
        private const double MinArmLen = 5;
        private const double MinLeafSize = 10;

        /// <summary>
        /// top-down approach
        /// </summary>
        /// <param name="canvas"></param>
        /// <param name="constraintRect"></param>
        /// <param name="orientation"></param>
        /// <param name="root"></param>
        /// <param name="scaleX"></param>
        /// <param name="scaleY"></param>
        /// <param name="dataBranches"></param>
        /// <param name="branchData"></param>
        public static void DrawDendrogram(
            Canvas canvas, 
            Rect constraintRect,
            Orientation orientation,
            BinaryHierarchicalData root,
            out double scaleX,
            out double scaleY,
            out Dictionary<BinaryHierarchicalData,Branch> dataBranches,
            out Dictionary<Branch,BinaryHierarchicalData> branchData)
        {
            scaleX = 1.0;
            scaleY = 1.0;
            dataBranches = new Dictionary<BinaryHierarchicalData, Branch>();
            branchData = new Dictionary<Branch, BinaryHierarchicalData>();
            double branchInterval = 1;
            double armLenScale = 1;
            double height = 20;
            UpdateLayoutSettings(
                LeafLength, orientation, root,
                ref constraintRect, ref height, ref branchInterval, ref armLenScale);
            AddBranch(canvas, orientation,constraintRect, new Point(0,0), 
                branchInterval,armLenScale,height,root,
                ref dataBranches, ref branchData);

            // top-down
            Branch rootBranch = dataBranches[root];
            Rect actualSize = UpdateBranchLayout(
                rootBranch, rootBranch.StartPos,
                dataBranches, branchData, branchInterval / 2);
            scaleX = actualSize.Width / canvas.Width;
            scaleY = actualSize.Height / canvas.Height;
            // bottom-up
            List<LeafData> orderedLeaves = new List<LeafData>();
            GetOrderedLeaves(root, ref orderedLeaves);
            UpdateParentBranchLayout(
                constraintRect, orientation, orderedLeaves, dataBranches);
        }

        private static void UpdateLayoutSettings(
            double leafLen,
            Orientation orientation,
            BinaryHierarchicalData root,
            ref Rect constraintRect,
            ref double height,
            ref double branchInterval,
            ref double armLenScale)
        {
            List<LeafData> leaves = BinaryHierarchicalDataUtil.GetLeavesForBranch(root);
            //if(orientation==Orientation.Horizontal)
            //{
            //    double minRequiredHeight = leaves.Count * MinLeafHeight + (leaves.Count+1)*Edge;
            //    double minRequiredWidth = root.Depth * MinBranchLen;
            //    if (minRequiredWidth > constraintRect.Width)
            //    {
            //        scaleX = constraintRect.Width / minRequiredWidth;
            //        constraintRect.Width = minRequiredWidth;
            //    }
            //    else
            //        scaleX = 1.0;
            //    if (minRequiredHeight > constraintRect.Height)
            //    {
            //        scaleY = constraintRect.Height / minRequiredHeight;
            //        constraintRect.Height = minRequiredHeight;
            //    }
            //    else
            //        scaleY = 1.0;
            //}
            //else
            //{
            //    double minRequiredWidth = leaves.Count * MinLeafHeight + (leaves.Count + 1) * Edge;
            //    double minRequiredHeight = root.Depth * MinBranchLen;
            //    if (minRequiredWidth > constraintRect.Width)
            //    {
            //        scaleX = constraintRect.Width / minRequiredWidth;
            //        constraintRect.Width = minRequiredWidth;
            //    }
            //    else
            //        scaleX = 1.0;
            //    if (minRequiredHeight > constraintRect.Height)
            //    {
            //        scaleY = constraintRect.Height / minRequiredHeight;
            //        constraintRect.Height = minRequiredHeight;
            //    }
            //    else
            //        scaleY = 1.0;
            //}
            int leavesCount = leaves.Count + 1;
            double maxDistance = 0;
            foreach (BinaryHierarchicalData child in root.Children)
            {
                if (child.DistanceToRoot > maxDistance)
                    maxDistance = child.DistanceToRoot;
            }
            int depth = root.Depth;
            if (orientation == System.Windows.Controls.Orientation.Horizontal)
            {
                height = (constraintRect.Width - leafLen) / depth;
                double leafInterval = constraintRect.Height / leavesCount - Edge;
                branchInterval = leafInterval*2+Edge;
                armLenScale = height / maxDistance;
            }
            else
            {
                height = (constraintRect.Height - leafLen) / depth;
                double leafInterval = constraintRect.Width / leavesCount - Edge;
                branchInterval = leafInterval*2 + Edge;
                armLenScale = height / maxDistance;
            }
        }

        private static void AddBranch(
            Canvas canvas, Orientation orientation, Rect constraint, Point startPos,
            double branchInterval, double neckLenScale, double height,
            BinaryHierarchicalData treeData,
            ref Dictionary<BinaryHierarchicalData, Branch> dataBranches,
            ref Dictionary<Branch,BinaryHierarchicalData> branchData)
        {
            Branch newBranch = CreateBranch(
                orientation, constraint, startPos, branchInterval, 
                neckLenScale, height, treeData);
            canvas.Children.Add(newBranch);
            branchData.Add(newBranch, treeData);
            dataBranches.Add(treeData,newBranch);
            double leftShoulderLen = 0;
            double rightShoulderLen = 0;
            if(treeData.LeftChild!=null)
            {
                int leftLeafCount = BinaryHierarchicalDataUtil.GetLeavesForBranch(treeData.LeftChild).Count;
                leftShoulderLen = leftLeafCount * branchInterval/2;
                Rect leftConstraint=new Rect(constraint.X+height,constraint.Y,constraint.Width-height, leftShoulderLen);
                if(orientation==Orientation.Vertical)
                {
                    leftConstraint=new Rect(constraint.X,constraint.Y+height, leftShoulderLen,constraint.Height-height);
                }
                AddBranch(canvas, orientation,leftConstraint,newBranch.LeftArmEnd,
                    branchInterval,neckLenScale,height,
                    treeData.LeftChild,ref dataBranches, ref branchData);
            }
            else
                leftShoulderLen = branchInterval;
            if(treeData.RightChild!=null)
            {
                int rightLeafCount = BinaryHierarchicalDataUtil.GetLeavesForBranch(treeData.RightChild).Count;
                rightShoulderLen = rightLeafCount * branchInterval/2;
                Rect rightConstraint=new Rect(constraint.X+height,constraint.Y+leftShoulderLen,constraint.Width-height,rightShoulderLen);
                if(orientation==Orientation.Vertical)
                    rightConstraint=new Rect(constraint.X+leftShoulderLen,constraint.Y+height,rightShoulderLen,constraint.Height-height);
                AddBranch(canvas, orientation,rightConstraint,newBranch.RightArmEnd,
                    branchInterval,neckLenScale,height,
                    treeData.RightChild,ref dataBranches,ref branchData);
            }
            else
                rightShoulderLen = branchInterval;
        }

        private static Branch CreateBranch(
            Orientation orientation,
            Rect constraingRect, 
            Point startPos,
            double branchInterval,
            double neckLenScale, double height,
            BinaryHierarchicalData treeData)
        {
            int leftLeafCount = treeData.LeftChild == null
                                    ? 1
                                    : BinaryHierarchicalDataUtil.GetLeafIDsForBranch(treeData.LeftChild).Count;
            int rightLeafCount = treeData.RightChild == null
                                     ? 1
                                     : BinaryHierarchicalDataUtil.GetLeafIDsForBranch(treeData.RightChild).Count;
            double leafInterval = branchInterval/2;
            double midPointHeight;
            if (leftLeafCount > 1 && rightLeafCount > 1)
            {
                midPointHeight = (
                                     leftLeafCount*leafInterval/2 +
                                     (leftLeafCount*leafInterval + (rightLeafCount*leafInterval)/2)
                                 )/2;
            }
            else if (leftLeafCount > 1 && rightLeafCount == 1)
            {
                midPointHeight = (
                                     leftLeafCount*leafInterval/2 +
                                     (leftLeafCount*leafInterval + leafInterval)
                                 )/2;
            }
            else if (leftLeafCount == 1 && rightLeafCount > 1)
            {
                midPointHeight = (
                                     leafInterval/2 +
                                     (leafInterval + (rightLeafCount*leafInterval)/2)
                                 )/2;
            }
            else
            {
                midPointHeight = leafInterval;
            }
            double armLen = treeData.Distance*neckLenScale;
            armLen = Math.Max(MinArmLen, armLen);
            double neckLen = height - armLen;
            neckLen = Math.Max(0, neckLen);
            double x = constraingRect.X;
            double y = constraingRect.Y + midPointHeight;
            if (orientation == Orientation.Vertical)
            {
                x = constraingRect.X + midPointHeight;
                y = constraingRect.Y;
            }
            if (startPos.X==0 && startPos.Y==0)
                startPos = new Point(x, y);
            double leftShoulderLen = leftLeafCount == 1 ? leafInterval : leafInterval*leftLeafCount/2;
            double rightShoulderLen = rightLeafCount == 1 ? leafInterval : leafInterval*rightLeafCount/2;
            double shoulderLen = (leftShoulderLen + rightShoulderLen)/2;
            Branch newBranch = new Branch(
                treeData, orientation, startPos,
                shoulderLen / 2, shoulderLen / 2, neckLen, armLen);

            return newBranch;
        }

        private static Rect UpdateBranchLayout(
            Branch branch, Point startPos, 
            Dictionary<BinaryHierarchicalData,Branch> dataBranches,
            Dictionary<Branch, BinaryHierarchicalData> branchData,
            double leafInterval)
        {
            Size leftChildSize=new Size(LeafLength,leafInterval);
            if(branchData[branch].LeftChild!=null)
            {
                leftChildSize = UpdateBranchSize(
                    dataBranches[branchData[branch].LeftChild],
                    leafInterval, branchData, dataBranches);
            }
            Size rightChildSize = new Size(LeafLength, leafInterval);
            if (branchData[branch].RightChild != null)
            {
                rightChildSize = UpdateBranchSize(
                    dataBranches[branchData[branch].RightChild],
                    leafInterval, branchData, dataBranches);
            }
            
            branch.UpdateLayout(startPos);
            BinaryHierarchicalData treeData = branchData[branch];
            
            if(treeData.LeftChild!=null)
            {
                Branch leftBranch = dataBranches[treeData.LeftChild];
                leftBranch.UpdateLayout(branch.LeftArmEnd);
            }
            if (treeData.RightChild!=null)
            {
                Branch rightBranch = dataBranches[treeData.RightChild];
                rightBranch.UpdateLayout(branch.RightArmEnd);
            }
            
            Rect bounds = new Rect(0,0, 
                Math.Max(leftChildSize.Width,rightChildSize.Width),
                Math.Max(leftChildSize.Height,rightChildSize.Height));
            return bounds;
        }

        private static Size UpdateBranchSize(Branch branch, 
            double leafInterval,
            Dictionary<Branch,BinaryHierarchicalData> branchData,
            Dictionary<BinaryHierarchicalData,Branch> dataBranches)
        {
            double w = 0;
            double h = 0;
            BinaryHierarchicalData treeData = branchData[branch];
            if(treeData.LeftChild==null)
                h += leafInterval;
            else
            {
                BinaryHierarchicalData leftTreeData = treeData.LeftChild;
                Branch leftBranch = dataBranches[leftTreeData];
                Size leftChildSize = UpdateBranchSize(leftBranch, leafInterval,branchData,dataBranches);
                w = Math.Max(w, leftChildSize.Width);
                h += leftChildSize.Height;
            }
            if(treeData.RightChild==null)
                h += leafInterval;
            else
            {
                BinaryHierarchicalData rightTreeData = treeData.RightChild;
                Branch rightBranch = dataBranches[rightTreeData];
                Size rightChildSize = UpdateBranchSize(rightBranch, leafInterval, branchData, dataBranches);
                w = Math.Max(w, rightChildSize.Width);
                h += rightChildSize.Height;
            }
            return new Size(w,h);
        }

        #region update branch from ordered leaves
        private static void GetOrderedLeaves(BinaryHierarchicalData root, ref List<LeafData> orderedLeaves)
        {
            if(root.LeftLeaf!=null)
            {
                if(!orderedLeaves.Contains(root.LeftLeaf))
                    orderedLeaves.Add(root.LeftLeaf);
            }
            if(root.LeftChild!=null)
                GetOrderedLeaves(root.LeftChild,ref orderedLeaves);
            if(root.RightLeaf!=null)
            {
                if(!orderedLeaves.Contains(root.RightLeaf))
                    orderedLeaves.Add(root.RightLeaf);
            }
            if (root.RightChild != null)
                GetOrderedLeaves(root.RightChild, ref orderedLeaves);
        }

        private static void UpdateParentBranchLayout(
            Rect bounds, Orientation orientation,
            List<LeafData> leaves, 
            Dictionary<BinaryHierarchicalData,Branch> dataBranches)
        {
            double interval = bounds.Height/leaves.Count;
            if (orientation == Orientation.Vertical)
                interval = bounds.Width/leaves.Count;
            if (interval < MinLeafSize)
                interval = MinLeafSize;
            Dictionary<LeafData,Rect> leafRects=new Dictionary<LeafData, Rect>();
            if(orientation==Orientation.Horizontal)
            {
                double fromX = bounds.X + bounds.Width - LeafLength;
                double fromY = bounds.Y;
                foreach (LeafData leaf in leaves)
                {
                    Rect leafRect = new Rect(fromX, fromY, LeafLength, interval);
                    leafRects.Add(leaf, leafRect);
                    fromY += interval;
                }
            }
            else
            {
                double fromX = bounds.X;
                double fromY = bounds.Y + bounds.Height - LeafLength;
                foreach(LeafData leaf in leaves)
                {
                    Rect leafRect=new Rect(fromX,fromY,interval,LeafLength);
                    leafRects.Add(leaf, leafRect);
                    fromX += interval;
                }
            }
            
            Dictionary<BinaryHierarchicalData, Point> processedBranchData= new Dictionary<BinaryHierarchicalData, Point>();
            List<BinaryHierarchicalData> parents = FindParentsForLeaves(leaves,processedBranchData,dataBranches);
            while(parents.Count>0)
            {
                foreach(BinaryHierarchicalData parent in parents)
                {
                    Point leftArmPos;
                    bool leftIsLeaf = false;
                    if(parent.LeftChild!=null)
                    {
                        if (processedBranchData.ContainsKey(parent.LeftChild))
                            leftArmPos = processedBranchData[parent.LeftChild];
                        else
                            leftArmPos = dataBranches[parent.LeftChild].StartPos;
                    }
                    else
                    {
                        leftIsLeaf = true;
                        Rect leafRect = leafRects[parent.LeftLeaf];
                        leftArmPos=new Point(leafRect.X, leafRect.Y+leafRect.Height/2);
                    }
                    bool rightIsLeaf = false;
                    Point rightArmPos;
                    if(parent.RightChild!=null)
                    {
                        if (processedBranchData.ContainsKey(parent.RightChild))
                            rightArmPos = processedBranchData[parent.RightChild];
                        else
                            rightArmPos = dataBranches[parent.RightChild].StartPos;
                    }
                    else
                    {
                        rightIsLeaf = true;
                        Rect leafRect = leafRects[parent.RightLeaf];
                        rightArmPos=new Point(leafRect.X,leafRect.Y+leafRect.Height/2);
                    }
                    Branch branch = dataBranches[parent];
                    Point branchStartPos = branch.UpdateLayout(leftArmPos, rightArmPos, leftIsLeaf, rightIsLeaf);
                    processedBranchData.Add(parent, branchStartPos);
                }

                parents = FindParentsForLeaves(leaves, processedBranchData, dataBranches);
            }
        }

        private static List<BinaryHierarchicalData> FindParentsForLeaves(
            List<LeafData> leaves,
            Dictionary<BinaryHierarchicalData, Point> processedBranchPositions,
            Dictionary<BinaryHierarchicalData, Branch> dataBranches)
        {
            List<BinaryHierarchicalData> parents = new List<BinaryHierarchicalData>();
            // leaf+leaf
            foreach (LeafData leaf in leaves)
            {
                if (parents.Contains(leaf.Parent) || processedBranchPositions.ContainsKey(leaf.Parent))
                    continue;

                LeafData otherLeaf = null;
                foreach (BinaryHierarchicalData treeData in dataBranches.Keys)
                {
                    if (treeData.LeftLeaf == leaf && treeData.RightLeaf != null)
                    {
                        otherLeaf = treeData.RightLeaf;
                        break;
                    }
                    if (treeData.RightLeaf == leaf && treeData.LeftLeaf != null)
                    {
                        otherLeaf = treeData.RightLeaf;
                        break;
                    }
                }
                if (otherLeaf != null && !parents.Contains(leaf.Parent) &&
                    !processedBranchPositions.ContainsKey(leaf.Parent))
                    parents.Add(leaf.Parent);
            }

            // leaf+branch
            foreach (LeafData leaf in leaves)
            {
                if (parents.Contains(leaf.Parent) || processedBranchPositions.ContainsKey(leaf.Parent))
                    continue;
                BinaryHierarchicalData parentFound = null;
                foreach (BinaryHierarchicalData treeData in dataBranches.Keys)
                {
                    if (parents.Contains(treeData) || processedBranchPositions.ContainsKey(treeData))
                        continue;

                    if (treeData.LeftLeaf == leaf && treeData.RightChild != null &&
                        processedBranchPositions.ContainsKey(treeData.RightChild))
                    {
                        parentFound = treeData;
                        break;
                    }
                    if (treeData.RightLeaf == leaf && treeData.LeftChild != null &&
                        processedBranchPositions.ContainsKey(treeData.LeftChild))
                    {
                        parentFound = treeData;
                        break;
                    }
                }

                if (parentFound != null && !parents.Contains(parentFound) &&
                    !processedBranchPositions.ContainsKey(parentFound))
                    parents.Add(parentFound);
            }

            // branch+branch
            foreach (BinaryHierarchicalData data in processedBranchPositions.Keys)
            {
                if (data.Parent == null)
                    continue;
                if (parents.Contains(data.Parent) || processedBranchPositions.ContainsKey(data.Parent))
                    continue;

                BinaryHierarchicalData sibling = null;
                foreach (BinaryHierarchicalData treeData in dataBranches.Keys)
                {
                    if (treeData.LeftChild == data && treeData.RightChild != null &&
                        processedBranchPositions.ContainsKey(treeData.RightChild))
                    {
                        sibling = treeData.RightChild;
                        break;
                    }
                    if (treeData.RightChild == data && treeData.LeftChild != null &&
                        processedBranchPositions.ContainsKey(treeData.LeftChild))
                    {
                        sibling = treeData.RightChild;
                        break;
                    }
                }
                if (sibling != null && !parents.Contains(data.Parent) &&
                    !processedBranchPositions.ContainsKey(data.Parent))
                    parents.Add(data.Parent);
            }
            return parents;
        }

        #endregion
    }
}
